Various types of spanning tree protocols are known (i.e., conventional spanning tree protocols). Such conventional spanning tree protocols serve to provide path redundancy for nodes of a network, while preventing any undesirable loop in the network. Examples of conventional spanning tree protocols include, but may not be limited to, Spanning Tree Protocol (STP), Rapid Spanning Tree Protocol (RSTP) and Multiple Spanning Tree Protocol (MSTP). STP is a legacy protocol in accordance with the IEEE 802.1D 1998 standard. RSTP is in accordance with IEEE 802.1D 2004 standard. MSTP is in accordance with the IEEE 802.1Q 2003 standard.
A particular process a spanning tree protocol performs when a change in topology occurs is referred to as convergence calculation, convergence or re-convergence. Examples of such topology changes include, but may not be limited to, a link failing and a bridge or bridge port being added to the topology. Such a convergence process comprises computing a new spanning tree from a root bridge to all bridges and designating some bridge ports as “forwarding” or “discarding”. Through this convergence process, a loop free topology is provided for. Once convergence is finished, the network node topology is stable and the implemented spanning tree protocol is in steady state, exchanging only hello message about every 2 seconds (i.e., referred as the “hello time”).
Avoiding loop in a network is an important task of a spanning tree protocol. When loop occurs, communication of information via an affected bridge or bridges quickly becomes very confusing and demanding of processing resources (e.g., central processing unit resources). If loop occurs, a bridge may see the same station (i.e., its own MAC address) on two different ports at the same time, thus misleading the forwarding engine as to which destination port packets should be sent.
Loop in a network also adversely impacts functionality and/or efficiency of Source Learning Protocol. Source Learning Protocol refers to a software or hardware processing, whose role is maintaining a Layer 2 bridging table (i.e., the Filtering database). This Layer 2 bridging table associates any learned, given MAC address to a given port in a given VLAN. In doing so, it allows Layer 2 forwarding processing to take place (i.e., sending a given frame to the correct port). When loop occurs, each time a station is learned on a port, if that same MAC address has been seen before on another port, the Source Learning Protocol software carries out “Mac Address Movement” processing whereby it updates the Layer 2 bridging table according to the most recent information available (i.e., finding an old MAC address, deleting it and creating a new MAC address).
Conventional spanning tree protocols such as, for example, STP, RSTP and MSTP inhibit flooding or bridging of Bridge Protocol Data Units (BPDUs) by hardware. As is the case, conventional spanning tree protocols are only implemented in software because of the complexity of the associated algorithm. Spanning tree protocol software is solely responsible for sending BPDUs across a network. This means that the more nodes there is in a given topology, the longer it takes to re-converge because each time a BPDU is received, it has to be processed by spanning tree protocol software before the spanning tree protocol software can in turn send the BPDUs on one or several ports.
Hardware transit time through a non-overloaded bridge is estimated around 5 microseconds for small frame data units such as BPDUs. Software processing time to process and send one or several BPDUs can be as low as 10-50 milliseconds, in the case the software is not overloaded. But, it can increase dramatically, when software is getting congested. Thus, with conventional implementations of spanning tree protocols, it is not practical or realistic to guaranty sub-x millisecond re-convergence times for all topology because software-processing time is usually not negligible as compare to hardware transit time.
Ethernet Automatic Protection Switching (EAPS) is a proprietary protocol offered by Extreme Network. EAPS offers resilient packet ring (RPR) functionality to provide sub-second fail-over protocol that allows a ring topology to re-converge without the use of spanning tree protocol functionality (i.e., IEEE 802.1D). Extreme Network's EAPS claims to provide a sub-50 ms recovery time, regardless of the number of nodes in a ring. However, it is probable that EAPS is subjected to transit time through all the nodes in a ring, which is accomplished via hardware to minimize the recovery delay. EAPS sends a “Topology Change” kind of frame in order to flush an associated forwarding table, thus allowing new topology to get learned. Accordingly, the claimed sub-50 ms re-convergence time likely does not take into account that processing of topology change across the entire ring (including flushing the L2 forwarding table) in order to relearn the right topology. Probably, activating a link known in advance as the backup link after a failure occurs in the ring is considered as re-convergence.
EAPS ports are excluded from participating to any spanning tree protocols in a particular VLAN. Thus, EAPS is clearly not compatible with any spanning tree protocol (e.g., STP RSTP or MSTP). EAPS relies on two distinct mechanisms: link down alerts and ring polling frames. EAPS elects a master node, which has a primary port and a secondary port. When a link down event occurs, the node that detects the link down event immediately sends a link down control frame toward the master node. The master node is also responsible for activating the backup link, which is its secondary link. The secondary link on a master node is normally blocked to insure a loop-free topology. After a failure, when the secondary link is up, the master node flushes its own forwarding table and also sends a control frame to all other ring nodes, instructing them to flush their forwarding tables. Ring polling frames are also used to monitor link failure. If a ring is safe, then each ring-polling frame is sent from the primary port and received on the secondary port. When a failure occurs, after the fail-period timer times out, the master node activates its secondary port and proceeds to the topology change kind or processing, in flushing its own forwarding table and in instructing the other nodes to do so (i.e., via the control frame). It can be seen that the ring polling mechanism is also used to provide a back-up mechanism in case the link down” mechanism fails when, for example, a link down frames gets lost.
Therefore, an implementation of spanning tree protocol that overcomes drawbacks associated with conventional implementations of spanning tree protocol would be useful, advantageous and novel.